SAS is a connection-oriented protocol that allows storage devices, like servers and disk drives, to communicate through a network of high-speed serial physical interconnects. Connections among the host devices—e.g., Host Bus Adapters (HBAs)—and target hard disk drives (HDDs) are managed by the intermediate devices called SAS expanders. The SAS expanders act as connection management agents, much like a switch element, having physical connections to multiple host devices or disk drives simultaneously.
The SAS protocol specifies a protocol stack that provides serial physical interconnect that can be used to connect together storage devices such HDDs and HBAs. SAS protocol specifies the transport layers protocols to transport SCSI commands, Serial Advanced Technology Attachment (alternatively Serial ATA or simply SATA) commands, and management commands among storage devices. The protocol is used in conjunction with SCSI and SATA command sets. The SAS protocol defines the function of a SAS expander device, which is part of the service delivery subsystem and facilities communication between SAS devices. In the general sense, the SAS expanders provide the switching and routing function among the SAS devices that are attached to the SAS expander.
Multiple SAS end devices and SAS expander devices can be connected together to form a SAS topology. There can be one or multiple physical links connecting each pair of the neighbouring devices. When there is a single physical link (i.e., “phy”) between two devices, the associated phy on the SAS device is called a narrow port which physical link has a dedicated SAS Address. When there are multiple physical links connecting two devices, the associated phys on an expander are considered to be a single wide port as all the associated phys are using the same dedicated SAS Address. In other words, all links of a wide port are considered to be a common logical link from a routing perspective, although it allows multiple simultaneous connections to pass through the wide port at the same time.
The SAS topology can be as simple as connecting multiple SAS end devices through a single SAS Expander device to an HBA, or as complex as connecting multiple SAS end devices through multiple SAS Expander devices to multiple HBA devices in a tree structure. Each SAS end device, SAS Expander device, and HBA device has a unique dedicated SAS Address. The connection between SAS end device to SAS Expander device or HBA device must be a narrow port whereas the connection between SAS expander devices or between SAS expander device and HBA device, can be a narrow port (one physical link) or a single wide port (multiple physical links).
The SAS protocol adopts the point-to-point connection mechanism. The SAS end device and HBA device have to communicate to each other through OPEN request. The OPEN request from a HBA device or SAS end device has to flow through a single SAS Expander device or multiple SAS Expander devices to reach the SAS end device or HBA device. The SAS Expander has to perform a point-to-point connection in order to route the OPEN request from the source phy to the target phy. The communication link is considered setup when an OPEN request from the SAS end device is accepted by the HBA device, or an OPEN request from the HBA device is accepted by the SAS end device. At this point, information can be transferred between the HBA device and SAS end device.
The OPEN requests from Multiple SAS end devices or HBA devices can reach the SAS Expander device at the same time. The SAS Expander has to resolve multiple OPEN requests targeted for different destination phys at the same time by connecting the request source phy to the target source phy one at a time according to the request priority. When there are multiple source phys requesting to be connected to the same target phy, an arbitration process is required to resolve the connection priority.
The SAS Expander device supports the least-recently used arbitration fairness as defined in SAS protocol. The least-recently used arbitration fairness is designed such that the longer the open request has been queuing up, the higher priority request will win the arbitration. The arbitration priority comprises three parameters: the Arbitration Wait Time (AWT), the request PHY SAS Address, and the Connection Rate (CONNRATE). The AWT indicates the amount of time the source phy has been waiting for the connection to the target phy. The Arbiter looks at the AWT, SAS Address, and Connection Rate in the ascending order when performing the arbitration. If two source phys that are queuing for the same target phy have the same AWT, the SAS Expander device looks at the SAS Address of the source phys. The source phy that has the largest SAS Address wins the arbitration. If both source phys have the same AWT and SAS Address, the source phy that has the highest connection rate wins the arbitration. In the case where the AWT, SAS Address, and CONNRATE are the same for the source phys, the SAS Expander device arbitrarily picks a winner from the source phys.
The AWT, SAS Address, and CONNRATE form the arbitration priority key for the request phy. If the SAS Expander device has N physical links, the SAS Expander device may receive up to N OPEN requests at the same time. Because the SAS topology adopts a point-to-point protocol, the SAS Expander device has to arbitrate and connect the crossbar by selecting the OPEN request phy with the highest priority key one at a time. The situation becomes more complicated as the SAS topology allows narrow port and wide port connection. If a physical link with the highest priority key is requesting a connection to the wide port whose physical links are also requesting but with lower priority keys, the SAS Expander has to connect the highest priority phy to the lowest priority phy within the wide port.
Arbitration rules are specified in the American National Standards Institute (ANSI) standard related to SAS, but the implementation is not explicitly specified nor readily apparent. The SAS expander is a connection-oriented switch/router based on the arbitration rules defined by the SAS standard. The number of physical links supported by the SAS expander and the adoption of an effective searching and sorting algorithm can significantly impact the cost and performance of the SAS expander, hence effecting the overall network performance.
There are no known techniques that address the connection management problem in SAS topology. While there are of course well know connection management algorithms for all kinds of circuit switches, SAS differs significantly from prior protocols due to the strategy of “reserve and wait” nature of handling routing congestion. Most of the prior protocols take “give up and retry” strategy in case of congestion so prior algorithms do not satisfy SAS topology requirements.
It is, therefore, desirable to provide an approach that provides connection management in the SAS topology.